/*
 * date: 2021/4/10
 * author: 2012190218 WangChenghua
 * used in main.cpp
 * --std c++14, MSVC.
 * this head file use separate compilation.
 * */
#include <iostream>
#include <string>
#include <fstream>
#include <cstdio>
using namespace std;

/*-----------------------Class of Single link list*/
template <typename T>
struct s_node{
    T data;
    struct s_node<T> *next;
};


template <typename ElemType>
class SingleLinkedList{
public:
    void InitList();
    void Insert_at_tail(ElemType x);
    void Print();
    void Insert_any_pos(int pos,ElemType x);
    void GetList(int pos);
    void Delete_pos(int pos);
    int FindList(ElemType x);
    int LengthList(){return head->data;}
    void ClearList();
    void ReverseList();

private:
    struct s_node<ElemType> *head;
    struct s_node<ElemType> *tail = head;
};


template<typename ElemType>
void SingleLinkedList<ElemType>::InitList(){
    head = new s_node<ElemType>;
    head->next = nullptr;
    head->data = 0; // head.data to count the node of this list;
    tail = head;
}


template<typename ElemType>
void SingleLinkedList<ElemType>::Insert_at_tail(ElemType x) {
    struct s_node<ElemType> *tmp = new s_node<ElemType>;
    tmp->next = nullptr;
    tmp->data = x;
    tail->next = tmp;
    tail = tmp;
    head->data++;
}


template<typename ElemType>
void SingleLinkedList<ElemType>::Print() {
    s_node<ElemType> *tmp = head;
    if(!tmp||!tmp->next){
        cout<<"empty"<<endl;
        return;
    }
    tmp = tmp->next;
    while(tmp){
        cout<<tmp->data<<"->";
        tmp = tmp->next;
    }
    cout<<"nullptr"<<endl;
}


template<typename ElemType>
void SingleLinkedList<ElemType>::Insert_any_pos(int pos, ElemType x) {
    int count = 0;
    s_node<ElemType> *tmp = head;
    if(pos<1||pos>head->data+1){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    while(tmp && count<pos-1){
        tmp = tmp->next;
        count++;
    }
    auto *NewNode = new s_node<ElemType>;
    NewNode->next = tmp->next;
    NewNode->data = x;
    tmp->next = NewNode;
    head->data++;
}


template<typename ElemType>
void SingleLinkedList<ElemType>::GetList(int pos) {
    if(pos<1||pos>head->data){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    struct s_node<ElemType> *tmp = head;
    int count=0;
    while(tmp && count!=pos){
        tmp = tmp->next;
        count++;
    }
    if(tmp) cout<<tmp->data<<endl;
    else cout<<"Don't exist!!!";
}


template<typename ElemType>
void SingleLinkedList<ElemType>::Delete_pos(int pos) {
    int count = 0;
    struct s_node<ElemType> *tmp = head;
    if(pos<1||pos>head->data+1){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    while(tmp && count<pos-1){
        count++;
        tmp = tmp->next;
    }
    struct s_node<ElemType> *buff = tmp->next;
    tmp->next = buff->next;
    delete buff;
}


template<typename ElemType>
int SingleLinkedList<ElemType>::FindList(ElemType x) {
    struct s_node<ElemType> *tmp = head;
    int count = 1;
    tmp = tmp->next;
    while(tmp && tmp->data!=x){
        tmp = tmp->next;
        count++;
    }
    if(tmp && tmp->data==x) return count;
    return -1;
}


template<typename ElemType>
void SingleLinkedList<ElemType>::ClearList() {
    //the head point would be stay.
    struct s_node<ElemType> *tmp = head;
    tmp = tmp->next;
    while(tmp){
        struct s_node<ElemType> *buff = tmp;
        tmp = tmp->next;
        delete buff;
    }
    head->next = nullptr;
}


template<typename Elemtype>
void SingleLinkedList<Elemtype>::ReverseList() {
    if(!head->next){
        cout<<"empty list,cant reverse!!!"<<endl;
        return;
    }
    struct s_node<Elemtype> *prev = nullptr;
    struct s_node<Elemtype> *curr = head->next;
    while (curr) {
        struct s_node<Elemtype> *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head->next = prev;
}

/*------------------Class double linked list------------*/
template <typename T>
struct d_node{
    T data;
    struct d_node<T> *next;
    struct d_node<T> *front;
};

template <typename ElemType>
class DuoLinkedList{
public:
    void InitList();
    void Insert_at_tail(ElemType x);
    void Print();
    void Insert_any_pos(int pos,ElemType x);
    void GetList(int pos);
    void Delete_pos(int pos);
    int FindList(ElemType x);
    int LengthList(){return head->data;}
    void ClearList();
private:
    struct d_node<ElemType> *head;
    struct d_node<ElemType> *tail = head;
};

template<typename ElemType>
void DuoLinkedList<ElemType>::InitList() {
    head = new d_node<ElemType>;
    head->data = 0;
    head->next = nullptr;
    head->front = nullptr;
    tail = head;
}

template<typename ElemType>
void DuoLinkedList<ElemType>::Insert_at_tail(ElemType x) {
    struct d_node<ElemType> *tmp = new d_node<ElemType>;
    tmp->next = nullptr;
    tmp->data = x;
    tail->next = tmp;
    tmp->front = tail;
    tail = tmp;
    head->data++;
}

template<typename ElemType>
void DuoLinkedList<ElemType>::Print() {
    d_node<ElemType> *tmp = head;
    if(!tmp||!tmp->next){
        cout<<"empty"<<endl;
        return;
    }
    tmp = tmp->next;
    while(tmp){
        cout<<tmp->data<<"<->";
        tmp = tmp->next;
    }
    cout<<"nullptr"<<endl;
}

template<typename ElemType>
void DuoLinkedList<ElemType>::Insert_any_pos(int pos, ElemType x) {
    int count = 0;
    d_node<ElemType> *tmp = head;
    if(pos<1||pos>head->data+1){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    while(tmp && count<pos-1){
        tmp = tmp->next;
        count++;
    }
    auto *NewNode = new d_node<ElemType>;
    NewNode->next = tmp->next;
    tmp->next->front = NewNode;
    NewNode->data = x;
    NewNode->front = tmp;
    tmp->next = NewNode;
    head->data++;
}

template<typename ElemType>
void DuoLinkedList<ElemType>::GetList(int pos) {
    if(pos<1||pos>head->data){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    struct d_node<ElemType> *tmp = head;
    int count=0;
    while(tmp && count!=pos){
        tmp = tmp->next;
        count++;
    }
    if(tmp) cout<<tmp->data<<endl;
    else cout<<"Don't exist!!!";
}

template<typename ElemType>
void DuoLinkedList<ElemType>::Delete_pos(int pos) {
    int count = 0;
    struct d_node<ElemType> *tmp = head;
    if(pos<1||pos>head->data+1){
        cout<<"position out of range!!!"<<endl;
        return;
    }
    while(tmp && count<pos-1){
        count++;
        tmp = tmp->next;
    }
    struct d_node<ElemType> *buff = tmp->next;
    tmp->next = buff->next;
    buff->next->front = tmp;
    delete buff;
}

template<typename ElemType>
int DuoLinkedList<ElemType>::FindList(ElemType x) {
    struct d_node<ElemType> *tmp = head;
    int count = 1;
    tmp = tmp->next;
    while(tmp && tmp->data!=x){
        tmp = tmp->next;
        count++;
    }
    if(tmp && tmp->data==x) return count;
    return -1;
}

template<typename ElemType>
void DuoLinkedList<ElemType>::ClearList() {
    //the head point would be stay.
    struct d_node<ElemType> *tmp = head;
    tmp = tmp->next;
    while(tmp){
        struct d_node<ElemType> *buff = tmp;
        tmp = tmp->next;
        delete buff;
    }
    head->next = nullptr;
}
/*------------------Class circle linked list---------*/
template<typename ElemType>
class CirLinkedList{
public:
    void InitList();
    void Insert_at_tails(ElemType x);
    void Print();
    bool Delete_data(ElemType x);

private:
    struct s_node<ElemType> *head;
    struct s_node<ElemType> *gt_tails;
};

template<typename ElemType>
void CirLinkedList<ElemType>::InitList() {
    head = gt_tails = nullptr;
}

template<typename ElemType>
void CirLinkedList<ElemType>::Insert_at_tails(ElemType x) {
    struct s_node<ElemType> *NewNode;
    NewNode = new s_node<ElemType>;
    NewNode->data = x;
    if(!head){
        head = NewNode;
        head->next = head;
        gt_tails = head;
    }else{
        NewNode->next = gt_tails->next;
        gt_tails->next =NewNode;
        gt_tails = NewNode;
    }
}

template<typename ElemType>
void CirLinkedList<ElemType>::Print() {
    struct s_node<ElemType> *tmp = head;
    if(tmp){
        do{
            cout<<tmp->data<<"->";
            tmp = tmp->next;
        }while(tmp!=head);
        cout<<endl;
    }else{
        cout<<"empty"<<endl;
        return;
    }
}

template<typename ElemType>
bool CirLinkedList<ElemType>::Delete_data(ElemType x) {
    gt_tails->next = nullptr;
    struct s_node<ElemType> *EmptyNode,*tmp,*pre,*buff;
    EmptyNode = new s_node<ElemType>;
    EmptyNode->next = head;
    tmp = EmptyNode->next;
    pre = EmptyNode;
    while(tmp){
        if(tmp->data==x){
            buff = tmp;
            tmp = pre->next = buff->next;
            delete buff;
        }else{
            tmp = tmp->next;
            pre = pre->next;
        }
    }
    gt_tails = pre;
    gt_tails->next = EmptyNode->next;
    head = EmptyNode->next;
    delete EmptyNode;
    return true;
}

/*--------------student system------------------------------*/
struct student{
    string name;
    string number;
    string s_class;
    int gender;
    struct student *next;
};

class Student{
public:
    /*-----student I/O--------*/
    void Readfile();
    void Writefile();
    void Print();
    void Find();
    /*-----student function---*/
    void InitList();
    void Insert_at_tail();
    int LengthList(){return head->gender;};
    void Delete();
private:
    struct student *head;
    struct student *tails;
    /*----student buffer------*/
    string buf_name,buf_number,buf_class;
    int buf_gender;
    /*----student I/O---------*/
    void IO_Insert();
    /*----student function----*/
    void Basic_insert_at_tail(string &a,string &b,string &c,int &d);
};
